#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
using namespace std;

class Solution {
public:

    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        for (int i = 0; i < nums.size(); i++)
        {
            if (i > 0 && nums[i] == nums[i - 1])
                continue;
            int l = i + 1;
            int r = nums.size() - 1;
            while (l < r)
            {
                if (nums[i] + nums[l] + nums[r] == 0)
                {
                    if (ans.empty() || (ans[ans.size() - 1] != vector({ nums[i],nums[l],nums[r] })))
                    {
                        ans.push_back({ nums[i],nums[l],nums[r] });
                    }
                    l++;
                    r--;
                }
                else {
                    if (nums[l] + nums[r] < -nums[i])
                        l = l + 1;
                    else r = r - 1;
                }
            }
        }
        return ans;
    }
};